package com.leo.m1803.d11;

import com.leo.common.TreeNode;

/**
 * Created by LEO on 2018/3/11.
 */
public class Offer06 {
    public static TreeNode reBuild(int[] pre, int[] in){
        return reBuild01(pre, 0, in, 0, in.length-1);
    }

    private static TreeNode reBuild01(int[] pre, int ps, int[] in, int is, int ie){
        if (ps < pre.length && is <= ie){
            int key = pre[ps];
            TreeNode node = new TreeNode(key);
            int pos = 0;
            for (int i = is; i <= ie; i++) {
                if (in[i] != key){ pos++; }
            }
            node.left = reBuild01(pre, ps+1, in, is, is+pos-1);
            node.right = reBuild01(pre, ps+pos+1, in, is+pos+1, ie);
            return node;
        }
        return null;
    }
}
